package com.star.entry.utils;

public class noob {
    private static final long MOD = 1_000_000_007;

    public static int Sequence(int n) {
        if (n == 1) return 0;
        if (n >= 2 && n <= 3) return 1;
        return Sequence(n - 3) + 2 * Sequence(n - 2) + Sequence(n - 1);
    }

    public static long fibonacciSequence(int i, int j) {


        long[][] dp = new long[i + 1][j + 1];
        //第一行和第一列均为1
        for (int m = 1; m <= i; m++) {
            dp[m][1] = 1;
        }
        for (int n = 1; n <= j; n++) {
            dp[1][n] = 1;
        }
        for (int m = 2; m <= i; m++) {
            for (int n = 2; n <= j; n++) {
                dp[m][n] = (dp[m - 1][n] + dp[m][n - 1]) % MOD;
            }
        }
        return dp[i][j];
    }
}
